//零钱兑换二  力扣518
//完全背包（每个物品可无限次选取）  放满背包有几种方法（放第i种物品的方法数+不放第i种物品的方法数）
//组合     先遍历物品，再遍历背包
//一维写法
class Solution {
public:
	int change(int amount, vector<int>& coins) {
		vector<uint64_t> dp(amount+1);
		//初始化
		for(int i = 0; i <= amount; i++)
			if(i % coins[0] == 0) dp[i] = 1;
		//递推
		for(int i = 1; i < coins.size(); i++)
		{
			for(int j = coins[i]; j <= amount; j++)
			{
				dp[j] = dp[j] + dp[j-coins[i]];
			}
		}
		return dp[amount];
	}
};
